{\magonebf 3.6 Bounded Queues (b\_queue) }

\decl b\_queue E

{\bf 1. Definition}

An instance $Q$ of the paramerized data type \name\ is a queue
(see section 2.4) of bounded size. 

\bigskip
{\bf 2. Creation}

\create Q (n)   

creates an instance \var\ of type \name\ that can hold up to $n$ elements.
\var\ is initialized with the empty queue.


\bigskip
{\bf 3. Operations}
\+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
\+\op E     top    {}       
                            { returns the front element of \var}
\+\nop                      { \precond $Q$ is not empty.}
\smallskip
\+\op E     pop    {}       
                            { deletes and returns the front element of \var}
\+\nop                      { \precond $Q$ is not empty.}
\smallskip
\+\op void  append {E\ x}   
                            { appends $x$ to the rear end of \var}
\+\nop                      { \precond $Q$.size()$ < n$.}
\smallskip
\+\op void  clear  {}       
                            { makes \var\ the empty queue.}
\smallskip
\+\op int   size   {}       
                            { returns the size of \var.}
\smallskip
\+\op bool  empty  {}       
                            { returns true if \var\ is empty, false otherwise.}
 
\bigskip
{\bf 4. Implementation}

Bounded Queues are implemented by circular arrays. All operations take 
time $O(1)$. The space requirement is $O(n)$.

